package leetcode.editor.cn;

//[152]乘积最大子数组
public class MaximumProductSubarray152 {
    public static void main(String[] args) {
        Solution solution = new MaximumProductSubarray152().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //执行耗时:3 ms,击败了24.53% 的Java用户 //	内存消耗:43.3 MB,击败了99.52% 的Java用户
        public int maxProduct(int[] nums) {
            if (nums == null || nums.length < 1) return -1;
            int res = nums[0];

            // 方式 1 应该有遗漏 0 。。。
            //fi 0 = max  = if  i < 0 , max 【 (f i-1 min * i) , i】
            //                  i > 0 , max 【 (f i-1 max * i) , i】
            //fi 1 = min  = if  i < 0 , min 【 (f i-1 max * i) , i】
            //                  i > 0 , min 【 (f i-1 min * i) , i】

            //TODO 方式 2 正确 不判断 i 正负， 只处理结果。 max ,min 下面这 3 个值。上面的有遗漏
            //      i * fi-1 min ,
            //      i * fi-1 max ,
            //      i,
            //TODO dp[n][0] = min ...dp[n-1]
            //TODO dp[n][1] = max ...dp[n-1]
            //
            // 如果其他的题目，可以不连续 再加上下面的 2 中选择，不 乘以 i
            //      fi-1 min ,
            //      fi-1 max ,


            int[][] dp = new int[nums.length][2];
            //[0] max
            //[1] min
            dp[0][0] = nums[0];
            dp[0][1] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                int cur = nums[i];
                int temp0 = dp[i - 1][0] * cur;
                int temp1 = dp[i - 1][1] * cur;
                int max = temp0 > temp1 ? (temp0 > cur ? temp0 : cur) : (temp1 > cur ? temp1 : cur);
                int min = temp0 < temp1 ? (temp0 < cur ? temp0 : cur) : (temp1 < cur ? temp1 : cur);

                res = max > res ? max : res;
                dp[i][0] = max;
                dp[i][1] = min;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}